package labuladong;

import java.util.HashMap;

public class Fibonacci {

    public static void main(String[] args) {
        System.out.println(fib(20));
    }

//    public static int fib(int n) {
//        if (n < 1) return 0;
//        // 备忘录全初始化为 0
//        HashMap<Integer,Integer> map = new HashMap<>();
//        map.put(n,0);
//        // 初始化最简情况
//        return helper(map, n);
//    }

    public static int helper(HashMap<Integer,Integer> map, int n) {
        // base case
        if (n == 1 || n == 2) return 1;
        // 已经计算过
        if (map.get(n)!=null&&map.get(n) != 0) return map.get(n);
        map.put(n,helper(map, n - 1) + helper(map, n - 2));
        return map.get(n);
    }

    /**
     * dp数组的迭代解法
     * @param n
     * @return
     */
    public static int fib(int n) {
        if(n==1||n==2)
            return 1;
        int prev=1,curr=1;
        for(int i=3;i<=n;i++){
            int sum = prev+curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }
}
